package com.hc.programming.tree;

import java.util.*;

/**
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 示例 1：
 * <a href="./二叉树的层序遍历-示例1.png">示例1</a>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * 示例 2：
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 * 输入：root = []
 * 输出：[]
 * <p>
 * 提示：
 * 树中节点数目在范围 [0, 2000] 内
 * -1000 <= Node.val <= 1000
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/9/6 11:29
 */
public class 二叉树的层序遍历 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{3, 9, 20, null, null, 15, 7};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=[[3],[9,20],[15,7]],--" + levelOrder(tree));
        arr = new Integer[]{1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=[[1], [2, 3], [4, 5, 8], [6, 7, 9]],--" + levelOrder(tree));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<>();
        if (root == null) return rst;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> row = new ArrayList<>();
            rst.add(row);
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                row.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);

            }
        }
        return rst;
    }
}
